class Solution {
    public int[] countBits(int n) {
        //Java相应的内置函数用于计算给定的整数的二进制表示中的 1的数目，Integer.bitCount
        //0:0(0)  1:1(1)  2:10(1)   3:11(2)  4:100(1)  5:101(2)  6:110(2)  7:111(3)  8:1000(1)  
        //9:1001(2)  10:1010(2)  11:1011(3)  12:1100(2)    13:1101(3)  14:1110(3)  15:1111(4)
        /*
        0
        1
        1  2
        1  2  2  3
        1  2  2  3  2  3  3  4
        */ 
        /*
        奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。
        偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移
        一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。
        所以我们可以得到如下的状态转移方程：
        dp[i] = dp[i-1]，当i为奇数
        dp[i] = dp[i/2]，当i为偶数
        合并为： dp[i] = dp[i/2] + i % 2
        i / 2 可以通过 i >> 1 得到；
        i % 2 可以通过 i & 1 得到；
        */
        int[] a = new int[n + 1];
        a[0] = 0;
        for(int i = 1;i <= n; i++) {
            a[i] = a[i >> 1] + (i & 1);
        }
        return a;
    }
}